package com.mooc.tree.bak.bst;

/**
 * @Author zhang.xin
 * @Description: TODO(这里描述)
 * @Date 2019/12/25
 */
public class BTSTree implements IBTSTree {

    BTSNode root;

    public BTSTree(){
        root = null;
    }

    /**
     * 递归的方式查询值
     * @param key 要查找的值
     * @param root 根节点
     * @return 该值得引用
     */
    public BTSNode find(int key, BTSNode root) {
        if (root == null)
            return null;

        if (key > root.getValue()) {
            return find(key, root.getRight());
        } else if (key < root.getValue()) {
            return find(key, root.getLeft());
        } else {
            return root;
        }
    }

    /**
     * 非递归的方式进行查找
     * @param key 待查找的值
     * @param root 根节点
     * @return 该值的引用
     */
    public BTSNode iterFind(int key, BTSNode root) {
        while (root != null) {
            if (key > root.getValue()) {
                root = root.getRight();
            } else if (key < root.getValue()) {
                root  = root.getLeft();
            } else {
                return root;
            }
        }
        return null;
    }

    /**
     * 平衡二叉树的最大值在最右分支的端节点上
     * @param root 根节点
     * @return 最大节点的引用
     */
    public BTSNode findMax(BTSNode root) {
        if (root == null)
            return  null;
        while (root.getRight() != null) {
            root = root.getRight();
        }
        return root;
    }

    /**
     * 平衡二叉树的最小节点，肯定在最左分支的端节点数
     * @param root
     * @return
     */
    public BTSNode findMin(BTSNode root) {
        if (root == null)
            return null;
        while (root.getLeft() != null) {
            root = root.getLeft();
        }
        return root;
    }

    public BTSNode insert(int key, BTSNode node) {
        if (root == null) {
            root = new BTSNode(key);
        }
        // todo
        return root;
    }

    public BTSNode delete(int key, BTSNode root) {
        return null;
    }
}
